#pragma once

#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>

#include "filippo.fantini.h"
#include "../common/basetypes.h"
#include "../common/MathUtils.h"
#include "../common/ProblemCommons.h"
#include "../common/bcd.h"

#include "NumberSpeller.h"

#define IsMultipleOf(n, m) ((n) % (m) == 0)

bool FilippoFantini::Init(Register& o_register)
{
	m_name = "FILIPPO FANTINI";

	REGISTER_FUNC(FilippoFantini, 1);
	REGISTER_FUNC(FilippoFantini, 2);
	REGISTER_FUNC(FilippoFantini, 3);
	REGISTER_FUNC(FilippoFantini, 5);
	REGISTER_FUNC(FilippoFantini, 6);
	REGISTER_FUNC(FilippoFantini, 7);
	REGISTER_FUNC(FilippoFantini, 10);
	REGISTER_FUNC(FilippoFantini, 13);
	REGISTER_FUNC(FilippoFantini, 14);
	REGISTER_FUNC(FilippoFantini, 15);
	REGISTER_FUNC(FilippoFantini, 16);
	REGISTER_FUNC(FilippoFantini, 17);
	REGISTER_FUNC(FilippoFantini, 18);
	REGISTER_FUNC(FilippoFantini, 20);
	REGISTER_FUNC(FilippoFantini, 22);
	REGISTER_FUNC(FilippoFantini, 25);
	REGISTER_FUNC(FilippoFantini, 28);
	REGISTER_FUNC(FilippoFantini, 40);
	REGISTER_FUNC(FilippoFantini, 42);
	//REGISTER_FUNC(FilippoFantini, 59); Takes about 1 minute
	REGISTER_FUNC(FilippoFantini, 67);

	return true;
}

namespace ZioUtils
{
	using namespace std;

	struct Node
	{
		Node(int pValue, Node* pLeft = NULL, Node* pRight = NULL)
		{
			left	= pLeft;
			right	= pRight;
			value	= pValue;
			best	= 0;
		}

		Node*		left;
		Node*		right;
		UInt64		value;
		UInt64		best;
	};

	UInt64 MaxRoute(Node* node)
	{
		if (!node->left && !node->right)
		{
			node->best = node->value;
		}
		else
		{
			node->best = max (  node->value + ((node->left->best != 0) ? node->left->best : MaxRoute(node->left)),
								node->value + ((node->right->best != 0) ? node->right->best : MaxRoute(node->right)) );
		}

		//std::cout << node->best << std::endl;

		return node->best;
	}

	void Tokenize(const string& str, vector<string>& tokens, const string& delimiters = " ")
	{
		string::size_type lastPos = str.find_first_not_of(delimiters, 0);
		string::size_type pos     = str.find_first_of(delimiters, lastPos);

		while (string::npos != pos || string::npos != lastPos)
		{
			tokens.push_back(str.substr(lastPos, pos - lastPos));
			lastPos = str.find_first_not_of(delimiters, pos);
			pos = str.find_first_of(delimiters, lastPos);
		}
	}
}

std::string decode(const std::string& text, const std::string& key)
{
	std::string::size_type textLength	= text.size();
	std::string::size_type keyLength	= key.size();

	const char* cstring = text.c_str();
	char* buffer = new char[textLength];

	// Copy the string while encripting
	for (unsigned i = 0; i < textLength; ++i)
		buffer[i] = cstring[i] ^ key.at(i % keyLength);

	return std::string(buffer, textLength);
}

RetType FilippoFantini::Problem59()
{
	using std::string;

	char textbytes[] = { 79,59,12,2,79,35,8,28,20,2,3,68,8,9,68,45,0,12,9,67,68,4,7,5,23,27,1,21,79,85,78,79,85,71,38,10,71,27,12,2,79,6,2,8,13,9,1,13,9,8,68,19,7,1,71,56,11,21,11,68,6,3,22,2,14,0,30,79,1,31,6,23,19,10,0,73,79,44,2,79,19,6,28,68,16,6,16,15,79,35,8,11,72,71,14,10,3,79,12,2,79,19,6,28,68,32,0,0,73,79,86,71,39,1,71,24,5,20,79,13,9,79,16,15,10,68,5,10,3,14,1,10,14,1,3,71,24,13,19,7,68,32,0,0,73,79,87,71,39,1,71,12,22,2,14,16,2,11,68,2,25,1,21,22,16,15,6,10,0,79,16,15,10,22,2,79,13,20,65,68,41,0,16,15,6,10,0,79,1,31,6,23,19,28,68,19,7,5,19,79,12,2,79,0,14,11,10,64,27,68,10,14,15,2,65,68,83,79,40,14,9,1,71,6,16,20,10,8,1,79,19,6,28,68,14,1,68,15,6,9,75,79,5,9,11,68,19,7,13,20,79,8,14,9,1,71,8,13,17,10,23,71,3,13,0,7,16,71,27,11,71,10,18,2,29,29,8,1,1,73,79,81,71,59,12,2,79,8,14,8,12,19,79,23,15,6,10,2,28,68,19,7,22,8,26,3,15,79,16,15,10,68,3,14,22,12,1,1,20,28,72,71,14,10,3,79,16,15,10,68,3,14,22,12,1,1,20,28,68,4,14,10,71,1,1,17,10,22,71,10,28,19,6,10,0,26,13,20,7,68,14,27,74,71,89,68,32,0,0,71,28,1,9,27,68,45,0,12,9,79,16,15,10,68,37,14,20,19,6,23,19,79,83,71,27,11,71,27,1,11,3,68,2,25,1,21,22,11,9,10,68,6,13,11,18,27,68,19,7,1,71,3,13,0,7,16,71,28,11,71,27,12,6,27,68,2,25,1,21,22,11,9,10,68,10,6,3,15,27,68,5,10,8,14,10,18,2,79,6,2,12,5,18,28,1,71,0,2,71,7,13,20,79,16,2,28,16,14,2,11,9,22,74,71,87,68,45,0,12,9,79,12,14,2,23,2,3,2,71,24,5,20,79,10,8,27,68,19,7,1,71,3,13,0,7,16,92,79,12,2,79,19,6,28,68,8,1,8,30,79,5,71,24,13,19,1,1,20,28,68,19,0,68,19,7,1,71,3,13,0,7,16,73,79,93,71,59,12,2,79,11,9,10,68,16,7,11,71,6,23,71,27,12,2,79,16,21,26,1,71,3,13,0,7,16,75,79,19,15,0,68,0,6,18,2,28,68,11,6,3,15,27,68,19,0,68,2,25,1,21,22,11,9,10,72,71,24,5,20,79,3,8,6,10,0,79,16,8,79,7,8,2,1,71,6,10,19,0,68,19,7,1,71,24,11,21,3,0,73,79,85,87,79,38,18,27,68,6,3,16,15,0,17,0,7,68,19,7,1,71,24,11,21,3,0,71,24,5,20,79,9,6,11,1,71,27,12,21,0,17,0,7,68,15,6,9,75,79,16,15,10,68,16,0,22,11,11,68,3,6,0,9,72,16,71,29,1,4,0,3,9,6,30,2,79,12,14,2,68,16,7,1,9,79,12,2,79,7,6,2,1,73,79,85,86,79,33,17,10,10,71,6,10,71,7,13,20,79,11,16,1,68,11,14,10,3,79,5,9,11,68,6,2,11,9,8,68,15,6,23,71,0,19,9,79,20,2,0,20,11,10,72,71,7,1,71,24,5,20,79,10,8,27,68,6,12,7,2,31,16,2,11,74,71,94,86,71,45,17,19,79,16,8,79,5,11,3,68,16,7,11,71,13,1,11,6,1,17,10,0,71,7,13,10,79,5,9,11,68,6,12,7,2,31,16,2,11,68,15,6,9,75,79,12,2,79,3,6,25,1,71,27,12,2,79,22,14,8,12,19,79,16,8,79,6,2,12,11,10,10,68,4,7,13,11,11,22,2,1,68,8,9,68,32,0,0,73,79,85,84,79,48,15,10,29,71,14,22,2,79,22,2,13,11,21,1,69,71,59,12,14,28,68,14,28,68,9,0,16,71,14,68,23,7,29,20,6,7,6,3,68,5,6,22,19,7,68,21,10,23,18,3,16,14,1,3,71,9,22,8,2,68,15,26,9,6,1,68,23,14,23,20,6,11,9,79,11,21,79,20,11,14,10,75,79,16,15,6,23,71,29,1,5,6,22,19,7,68,4,0,9,2,28,68,1,29,11,10,79,35,8,11,74,86,91,68,52,0,68,19,7,1,71,56,11,21,11,68,5,10,7,6,2,1,71,7,17,10,14,10,71,14,10,3,79,8,14,25,1,3,79,12,2,29,1,71,0,10,71,10,5,21,27,12,71,14,9,8,1,3,71,26,23,73,79,44,2,79,19,6,28,68,1,26,8,11,79,11,1,79,17,9,9,5,14,3,13,9,8,68,11,0,18,2,79,5,9,11,68,1,14,13,19,7,2,18,3,10,2,28,23,73,79,37,9,11,68,16,10,68,15,14,18,2,79,23,2,10,10,71,7,13,20,79,3,11,0,22,30,67,68,19,7,1,71,8,8,8,29,29,71,0,2,71,27,12,2,79,11,9,3,29,71,60,11,9,79,11,1,79,16,15,10,68,33,14,16,15,10,22,73 };
	const char* words[] = { "A","ABILITY","ABLE","ABOUT","ABOVE","ABSENCE","ABSOLUTELY","ACADEMIC","ACCEPT","ACCESS","ACCIDENT","ACCOMPANY","ACCORDING","ACCOUNT","ACHIEVE","ACHIEVEMENT","ACID","ACQUIRE","ACROSS","ACT","ACTION","ACTIVE","ACTIVITY","ACTUAL","ACTUALLY","ADD","ADDITION","ADDITIONAL","ADDRESS","ADMINISTRATION","ADMIT","ADOPT","ADULT","ADVANCE","ADVANTAGE","ADVICE","ADVISE","AFFAIR","AFFECT","AFFORD","AFRAID","AFTER","AFTERNOON","AFTERWARDS","AGAIN","AGAINST","AGE","AGENCY","AGENT","AGO","AGREE","AGREEMENT","AHEAD","AID","AIM","AIR","AIRCRAFT","ALL","ALLOW","ALMOST","ALONE","ALONG","ALREADY","ALRIGHT","ALSO","ALTERNATIVE","ALTHOUGH","ALWAYS","AMONG","AMONGST","AMOUNT","AN","ANALYSIS","ANCIENT","AND","ANIMAL","ANNOUNCE","ANNUAL","ANOTHER","ANSWER","ANY","ANYBODY","ANYONE","ANYTHING","ANYWAY","APART","APPARENT","APPARENTLY","APPEAL","APPEAR","APPEARANCE","APPLICATION","APPLY","APPOINT","APPOINTMENT","APPROACH","APPROPRIATE","APPROVE","AREA","ARGUE","ARGUMENT","ARISE","ARM","ARMY","AROUND","ARRANGE","ARRANGEMENT","ARRIVE","ART","ARTICLE","ARTIST","AS","ASK","ASPECT","ASSEMBLY","ASSESS","ASSESSMENT","ASSET","ASSOCIATE","ASSOCIATION","ASSUME","ASSUMPTION","AT","ATMOSPHERE","ATTACH","ATTACK","ATTEMPT","ATTEND","ATTENTION","ATTITUDE","ATTRACT","ATTRACTIVE","AUDIENCE","AUTHOR","AUTHORITY","AVAILABLE","AVERAGE","AVOID","AWARD","AWARE","AWAY","AYE","BABY","BACK","BACKGROUND","BAD","BAG","BALANCE","BALL","BAND","BANK","BAR","BASE","BASIC","BASIS","BATTLE","BE","BEAR","BEAT","BEAUTIFUL","BECAUSE","BECOME","BED","BEDROOM","BEFORE","BEGIN","BEGINNING","BEHAVIOUR","BEHIND","BELIEF","BELIEVE","BELONG","BELOW","BENEATH","BENEFIT","BESIDE","BEST","BETTER","BETWEEN","BEYOND","BIG","BILL","BIND","BIRD","BIRTH","BIT","BLACK","BLOCK","BLOOD","BLOODY","BLOW","BLUE","BOARD","BOAT","BODY","BONE","BOOK","BORDER","BOTH","BOTTLE","BOTTOM","BOX","BOY","BRAIN","BRANCH","BREAK","BREATH","BRIDGE","BRIEF","BRIGHT","BRING","BROAD","BROTHER","BUDGET","BUILD","BUILDING","BURN","BUS","BUSINESS","BUSY","BUT","BUY","BY","CABINET","CALL","CAMPAIGN","CAN","CANDIDATE","CAPABLE","CAPACITY","CAPITAL","CAR","CARD","CARE","CAREER","CAREFUL","CAREFULLY","CARRY","CASE","CASH","CAT","CATCH","CATEGORY","CAUSE","CELL","CENTRAL","CENTRE","CENTURY","CERTAIN","CERTAINLY","CHAIN","CHAIR","CHAIRMAN","CHALLENGE","CHANCE","CHANGE","CHANNEL","CHAPTER","CHARACTER","CHARACTERISTIC","CHARGE","CHEAP","CHECK","CHEMICAL","CHIEF","CHILD","CHOICE","CHOOSE","CHURCH","CIRCLE","CIRCUMSTANCE","CITIZEN","CITY","CIVIL","CLAIM","CLASS","CLEAN","CLEAR","CLEARLY","CLIENT","CLIMB","CLOSE","CLOSELY","CLOTHES","CLUB","COAL","CODE","COFFEE","COLD","COLLEAGUE","COLLECT","COLLECTION","COLLEGE","COLOUR","COMBINATION","COMBINE","COME","COMMENT","COMMERCIAL","COMMISSION","COMMIT","COMMITMENT","COMMITTEE","COMMON","COMMUNICATION","COMMUNITY","COMPANY","COMPARE","COMPARISON","COMPETITION","COMPLETE","COMPLETELY","COMPLEX","COMPONENT","COMPUTER","CONCENTRATE","CONCENTRATION","CONCEPT","CONCERN","CONCERNED","CONCLUDE","CONCLUSION","CONDITION","CONDUCT","CONFERENCE","CONFIDENCE","CONFIRM","CONFLICT","CONGRESS","CONNECT","CONNECTION","CONSEQUENCE","CONSERVATIVE","CONSIDER","CONSIDERABLE","CONSIDERATION","CONSIST","CONSTANT","CONSTRUCTION","CONSUMER","CONTACT","CONTAIN","CONTENT","CONTEXT","CONTINUE","CONTRACT","CONTRAST","CONTRIBUTE","CONTRIBUTION","CONTROL","CONVENTION","CONVERSATION","COPY","CORNER","CORPORATE","CORRECT","COS","COST","COULD","COUNCIL","COUNT","COUNTRY","COUNTY","COUPLE","COURSE","COURT","COVER","CREATE","CREATION","CREDIT","CRIME","CRIMINAL","CRISIS","CRITERION","CRITICAL","CRITICISM","CROSS","CROWD","CRY","CULTURAL","CULTURE","CUP","CURRENT","CURRENTLY","CURRICULUM","CUSTOMER","CUT","DAMAGE","DANGER","DANGEROUS","DARK","DATA","DATE","DAUGHTER","DAY","DEAD","DEAL","DEATH","DEBATE","DEBT","DECADE","DECIDE","DECISION","DECLARE","DEEP","DEFENCE","DEFENDANT","DEFINE","DEFINITION","DEGREE","DELIVER","DEMAND","DEMOCRATIC","DEMONSTRATE","DENY","DEPARTMENT","DEPEND","DEPUTY","DERIVE","DESCRIBE","DESCRIPTION","DESIGN","DESIRE","DESK","DESPITE","DESTROY","DETAIL","DETAILED","DETERMINE","DEVELOP","DEVELOPMENT","DEVICE","DIE","DIFFERENCE","DIFFERENT","DIFFICULT","DIFFICULTY","DINNER","DIRECT","DIRECTION","DIRECTLY","DIRECTOR","DISAPPEAR","DISCIPLINE","DISCOVER","DISCUSS","DISCUSSION","DISEASE","DISPLAY","DISTANCE","DISTINCTION","DISTRIBUTION","DISTRICT","DIVIDE","DIVISION","DO","DOCTOR","DOCUMENT","DOG","DOMESTIC","DOOR","DOUBLE","DOUBT","DOWN","DRAW","DRAWING","DREAM","DRESS","DRINK","DRIVE","DRIVER","DROP","DRUG","DRY","DUE","DURING","DUTY","EACH","EAR","EARLY","EARN","EARTH","EASILY","EAST","EASY","EAT","ECONOMIC","ECONOMY","EDGE","EDITOR","EDUCATION","EDUCATIONAL","EFFECT","EFFECTIVE","EFFECTIVELY","EFFORT","EGG","EITHER","ELDERLY","ELECTION","ELEMENT","ELSE","ELSEWHERE","EMERGE","EMPHASIS","EMPLOY","EMPLOYEE","EMPLOYER","EMPLOYMENT","EMPTY","ENABLE","ENCOURAGE","END","ENEMY","ENERGY","ENGINE","ENGINEERING","ENJOY","ENOUGH","ENSURE","ENTER","ENTERPRISE","ENTIRE","ENTIRELY","ENTITLE","ENTRY","ENVIRONMENT","ENVIRONMENTAL","EQUAL","EQUALLY","EQUIPMENT","ERROR","ESCAPE","ESPECIALLY","ESSENTIAL","ESTABLISH","ESTABLISHMENT","ESTATE","ESTIMATE","EVEN","EVENING","EVENT","EVENTUALLY","EVER","EVERY","EVERYBODY","EVERYONE","EVERYTHING","EVIDENCE","EXACTLY","EXAMINATION","EXAMINE","EXAMPLE","EXCELLENT","EXCEPT","EXCHANGE","EXECUTIVE","EXERCISE","EXHIBITION","EXIST","EXISTENCE","EXISTING","EXPECT","EXPECTATION","EXPENDITURE","EXPENSE","EXPENSIVE","EXPERIENCE","EXPERIMENT","EXPERT","EXPLAIN","EXPLANATION","EXPLORE","EXPRESS","EXPRESSION","EXTEND","EXTENT","EXTERNAL","EXTRA","EXTREMELY","EYE","FACE","FACILITY","FACT","FACTOR","FACTORY","FAIL","FAILURE","FAIR","FAIRLY","FAITH","FALL","FAMILIAR","FAMILY","FAMOUS","FAR","FARM","FARMER","FASHION","FAST","FATHER","FAVOUR","FEAR","FEATURE","FEE","FEEL","FEELING","FEMALE","FEW","FIELD","FIGHT","FIGURE","FILE","FILL","FILM","FINAL","FINALLY","FINANCE","FINANCIAL","FIND","FINDING","FINE","FINGER","FINISH","FIRE","FIRM","FIRST","FISH","FIT","FIX","FLAT","FLIGHT","FLOOR","FLOW","FLOWER","FLY","FOCUS","FOLLOW","FOLLOWING","FOOD","FOOT","FOOTBALL","FOR","FORCE","FOREIGN","FOREST","FORGET","FORM","FORMAL","FORMER","FORWARD","FOUNDATION","FREE","FREEDOM","FREQUENTLY","FRESH","FRIEND","FROM","FRONT","FRUIT","FUEL","FULL","FULLY","FUNCTION","FUND","FUNNY","FURTHER","FUTURE","GAIN","GAME","GARDEN","GAS","GATE","GATHER","GENERAL","GENERALLY","GENERATE","GENERATION","GENTLEMAN","GET","GIRL","GIVE","GLASS","GO","GOAL","GOD","GOLD","GOOD","GOVERNMENT","GRANT","GREAT","GREEN","GREY","GROUND","GROUP","GROW","GROWING","GROWTH","GUEST","GUIDE","GUN","HAIR","HALF","HALL","HAND","HANDLE","HANG","HAPPEN","HAPPY","HARD","HARDLY","HATE","HAVE","HE","HEAD","HEALTH","HEAR","HEART","HEAT","HEAVY","HELL","HELP","HENCE","HER","HERE","HERSELF","HIDE","HIGH","HIGHLY","HILL","HIM","HIMSELF","HIS","HISTORICAL","HISTORY","HIT","HOLD","HOLE","HOLIDAY","HOME","HOPE","HORSE","HOSPITAL","HOT","HOTEL","HOUR","HOUSE","HOUSEHOLD","HOUSING","HOW","HOWEVER","HUGE","HUMAN","HURT","HUSBAND","I","IDEA","IDENTIFY","IF","IGNORE","ILLUSTRATE","IMAGE","IMAGINE","IMMEDIATE","IMMEDIATELY","IMPACT","IMPLICATION","IMPLY","IMPORTANCE","IMPORTANT","IMPOSE","IMPOSSIBLE","IMPRESSION","IMPROVE","IMPROVEMENT","IN","INCIDENT","INCLUDE","INCLUDING","INCOME","INCREASE","INCREASED","INCREASINGLY","INDEED","INDEPENDENT","INDEX","INDICATE","INDIVIDUAL","INDUSTRIAL","INDUSTRY","INFLUENCE","INFORM","INFORMATION","INITIAL","INITIATIVE","INJURY","INSIDE","INSIST","INSTANCE","INSTEAD","INSTITUTE","INSTITUTION","INSTRUCTION","INSTRUMENT","INSURANCE","INTEND","INTENTION","INTEREST","INTERESTED","INTERESTING","INTERNAL","INTERNATIONAL","INTERPRETATION","INTERVIEW","INTO","INTRODUCE","INTRODUCTION","INVESTIGATE","INVESTIGATION","INVESTMENT","INVITE","INVOLVE","IRON","IS","ISLAND","ISSUE","IT","ITEM","ITS","ITSELF","JOB","JOIN","JOINT","JOURNEY","JUDGE","JUMP","JUST","JUSTICE","KEEP","KEY","KID","KILL","KIND","KING","KITCHEN","KNEE","KNOW","KNOWLEDGE","LABOUR","LACK","LADY","LAND","LANGUAGE","LARGE","LARGELY","LAST","LATE","LATER","LATTER","LAUGH","LAUNCH","LAW","LAWYER","LAY","LEAD","LEADER","LEADERSHIP","LEADING","LEAF","LEAGUE","LEAN","LEARN","LEAST","LEAVE","LEFT","LEG","LEGAL","LEGISLATION","LENGTH","LESS","LET","LETTER","LEVEL","LIABILITY","LIBERAL","LIBRARY","LIE","LIFE","LIFT","LIGHT","LIKE","LIKELY","LIMIT","LIMITED","LINE","LINK","LIP","LIST","LISTEN","LITERATURE","LITTLE","LIVE","LIVING","LOAN","LOCAL","LOCATION","LONG","LOOK","LORD","LOSE","LOSS","LOT","LOVE","LOVELY","LOW","LUNCH","MACHINE","MAGAZINE","MAIN","MAINLY","MAINTAIN","MAJOR","MAJORITY","MAKE","MALE","MAN","MANAGE","MANAGEMENT","MANAGER","MANNER","MANY","MAP","MARK","MARKET","MARRIAGE","MARRIED","MARRY","MASS","MASTER","MATCH","MATERIAL","MATTER","MAY","MAYBE","ME","MEAL","MEAN","MEANING","MEANS","MEANWHILE","MEASURE","MECHANISM","MEDIA","MEDICAL","MEET","MEETING","MEMBER","MEMBERSHIP","MEMORY","MENTAL","MENTION","MERELY","MESSAGE","METAL","METHOD","MIDDLE","MIGHT","MILE","MILITARY","MILK","MIND","MINE","MINISTER","MINISTRY","MINUTE","MISS","MISTAKE","MODEL","MODERN","MODULE","MOMENT","MONEY","MONTH","MORE","MORNING","MOST","MOTHER","MOTION","MOTOR","MOUNTAIN","MOUTH","MOVE","MOVEMENT","MUCH","MURDER","MUSEUM","MUSIC","MUST","MY","MYSELF","NAME","NARROW","NATION","NATIONAL","NATURAL","NATURE","NEAR","NEARLY","NECESSARILY","NECESSARY","NECK","NEED","NEGOTIATION","NEIGHBOUR","NEITHER","NETWORK","NEVER","NEVERTHELESS","NEW","NEWS","NEWSPAPER","NEXT","NICE","NIGHT","NO","NOBODY","NOD","NOISE","NONE","NOR","NORMAL","NORMALLY","NORTH","NORTHERN","NOSE","NOT","NOTE","NOTHING","NOTICE","NOTION","NOW","NUCLEAR","NUMBER","NURSE","OBJECT","OBJECTIVE","OBSERVATION","OBSERVE","OBTAIN","OBVIOUS","OBVIOUSLY","OCCASION","OCCUR","ODD","OF","OFF","OFFENCE","OFFER","OFFICE","OFFICER","OFFICIAL","OFTEN","OIL","OKAY","OLD","ON","ONCE","ONE","ONLY","ONTO","OPEN","OPERATE","OPERATION","OPINION","OPPORTUNITY","OPPOSITION","OPTION","OR","ORDER","ORDINARY","ORGANISATION","ORGANISE","ORGANIZATION","ORIGIN","ORIGINAL","OTHER","OTHERWISE","OUGHT","OUR","OURSELVES","OUT","OUTCOME","OUTPUT","OUTSIDE","OVER","OVERALL","OWN","OWNER","PACKAGE","PAGE","PAIN","PAINT","PAINTING","PAIR","PANEL","PAPER","PARENT","PARK","PARLIAMENT","PART","PARTICULAR","PARTICULARLY","PARTLY","PARTNER","PARTY","PASS","PASSAGE","PAST","PATH","PATIENT","PATTERN","PAY","PAYMENT","PEACE","PENSION","PEOPLE","PER","PERCENT","PERFECT","PERFORM","PERFORMANCE","PERHAPS","PERIOD","PERMANENT","PERSON","PERSONAL","PERSUADE","PHASE","PHONE","PHOTOGRAPH","PHYSICAL","PICK","PICTURE","PIECE","PLACE","PLAN","PLANNING","PLANT","PLASTIC","PLATE","PLAY","PLAYER","PLEASE","PLEASURE","PLENTY","PLUS","POCKET","POINT","POLICE","POLICY","POLITICAL","POLITICS","POOL","POOR","POPULAR","POPULATION","POSITION","POSITIVE","POSSIBILITY","POSSIBLE","POSSIBLY","POST","POTENTIAL","POUND","POWER","POWERFUL","PRACTICAL","PRACTICE","PREFER","PREPARE","PRESENCE","PRESENT","PRESIDENT","PRESS","PRESSURE","PRETTY","PREVENT","PREVIOUS","PREVIOUSLY","PRICE","PRIMARY","PRIME","PRINCIPLE","PRIORITY","PRISON","PRISONER","PRIVATE","PROBABLY","PROBLEM","PROCEDURE","PROCESS","PRODUCE","PRODUCT","PRODUCTION","PROFESSIONAL","PROFIT","PROGRAM","PROGRAMME","PROGRESS","PROJECT","PROMISE","PROMOTE","PROPER","PROPERLY","PROPERTY","PROPORTION","PROPOSE","PROPOSAL","PROSPECT","PROTECT","PROTECTION","PROVE","PROVIDE","PROVIDED","PROVISION","PUB","PUBLIC","PUBLICATION","PUBLISH","PULL","PUPIL","PURPOSE","PUSH","PUT","QUALITY","QUARTER","QUESTION","QUICK","QUICKLY","QUIET","QUITE","RACE","RADIO","RAILWAY","RAIN","RAISE","RANGE","RAPIDLY","RARE","RATE","RATHER","REACH","REACTION","READ","READER","READING","READY","REAL","REALISE","REALITY","REALIZE","REALLY","REASON","REASONABLE","RECALL","RECEIVE","RECENT","RECENTLY","RECOGNISE","RECOGNITION","RECOGNIZE","RECOMMEND","RECORD","RECOVER","RED","REDUCE","REDUCTION","REFER","REFERENCE","REFLECT","REFORM","REFUSE","REGARD","REGION","REGIONAL","REGULAR","REGULATION","REJECT","RELATE","RELATION","RELATIONSHIP","RELATIVE","RELATIVELY","RELEASE","RELEVANT","RELIEF","RELIGION","RELIGIOUS","RELY","REMAIN","REMEMBER","REMIND","REMOVE","REPEAT","REPLACE","REPLY","REPORT","REPRESENT","REPRESENTATION","REPRESENTATIVE","REQUEST","REQUIRE","REQUIREMENT","RESEARCH","RESOURCE","RESPECT","RESPOND","RESPONSE","RESPONSIBILITY","RESPONSIBLE","REST","RESTAURANT","RESULT","RETAIN","RETURN","REVEAL","REVENUE","REVIEW","REVOLUTION","RICH","RIDE","RIGHT","RING","RISE","RISK","RIVER","ROAD","ROCK","ROLE","ROLL","ROOF","ROOM","ROUND","ROUTE","ROW","ROYAL","RULE","RUN","RURAL","SAFE","SAFETY","SALE","SAME","SAMPLE","SATISFY","SAVE","SAY","SCALE","SCENE","SCHEME","SCHOOL","SCIENCE","SCIENTIFIC","SCIENTIST","SCORE","SCREEN","SEA","SEARCH","SEASON","SEAT","SECOND","SECONDARY","SECRETARY","SECTION","SECTOR","SECURE","SECURITY","SEE","SEEK","SEEM","SELECT","SELECTION","SELL","SEND","SENIOR","SENSE","SENTENCE","SEPARATE","SEQUENCE","SERIES","SERIOUS","SERIOUSLY","SERVANT","SERVE","SERVICE","SESSION","SET","SETTLE","SETTLEMENT","SEVERAL","SEVERE","SEX","SEXUAL","SHAKE","SHALL","SHAPE","SHARE","SHE","SHEET","SHIP","SHOE","SHOOT","SHOP","SHORT","SHOT","SHOULD","SHOULDER","SHOUT","SHOW","SHUT","SIDE","SIGHT","SIGN","SIGNAL","SIGNIFICANCE","SIGNIFICANT","SILENCE","SIMILAR","SIMPLE","SIMPLY","SINCE","SING","SINGLE","SIR","SISTER","SIT","SITE","SITUATION","SIZE","SKILL","SKIN","SKY","SLEEP","SLIGHTLY","SLIP","SLOW","SLOWLY","SMALL","SMILE","SO","SOCIAL","SOCIETY","SOFT","SOFTWARE","SOIL","SOLDIER","SOLICITOR","SOLUTION","SOME","SOMEBODY","SOMEONE","SOMETHING","SOMETIMES","SOMEWHAT","SOMEWHERE","SON","SONG","SOON","SORRY","SORT","SOUND","SOURCE","SOUTH","SOUTHERN","SPACE","SPEAK","SPEAKER","SPECIAL","SPECIES","SPECIFIC","SPEECH","SPEED","SPEND","SPIRIT","SPORT","SPOT","SPREAD","SPRING","STAFF","STAGE","STAND","STANDARD","STAR","START","STATE","STATEMENT","STATION","STATUS","STAY","STEAL","STEP","STICK","STILL","STOCK","STONE","STOP","STORE","STORY","STRAIGHT","STRANGE","STRATEGY","STREET","STRENGTH","STRIKE","STRONG","STRONGLY","STRUCTURE","STUDENT","STUDIO","STUDY","STUFF","STYLE","SUBJECT","SUBSTANTIAL","SUCCEED","SUCCESS","SUCCESSFUL","SUCH","SUDDENLY","SUFFER","SUFFICIENT","SUGGEST","SUGGESTION","SUITABLE","SUM","SUMMER","SUN","SUPPLY","SUPPORT","SUPPOSE","SURE","SURELY","SURFACE","SURPRISE","SURROUND","SURVEY","SURVIVE","SWITCH","SYSTEM","TABLE","TAKE","TALK","TALL","TAPE","TARGET","TASK","TAX","TEA","TEACH","TEACHER","TEACHING","TEAM","TEAR","TECHNICAL","TECHNIQUE","TECHNOLOGY","TELEPHONE","TELEVISION","TELL","TEMPERATURE","TEND","TERM","TERMS","TERRIBLE","TEST","TEXT","THAN","THANK","THANKS","THAT","THE","THEATRE","THEIR","THEM","THEME","THEMSELVES","THEN","THEORY","THERE","THEREFORE","THESE","THEY","THIN","THING","THINK","THIS","THOSE","THOUGH","THOUGHT","THREAT","THREATEN","THROUGH","THROUGHOUT","THROW","THUS","TICKET","TIME","TINY","TITLE","TO","TODAY","TOGETHER","TOMORROW","TONE","TONIGHT","TOO","TOOL","TOOTH","TOP","TOTAL","TOTALLY","TOUCH","TOUR","TOWARDS","TOWN","TRACK","TRADE","TRADITION","TRADITIONAL","TRAFFIC","TRAIN","TRAINING","TRANSFER","TRANSPORT","TRAVEL","TREAT","TREATMENT","TREATY","TREE","TREND","TRIAL","TRIP","TROOP","TROUBLE","TRUE","TRUST","TRUTH","TRY","TURN","TWICE","TYPE","TYPICAL","UNABLE","UNDER","UNDERSTAND","UNDERSTANDING","UNDERTAKE","UNEMPLOYMENT","UNFORTUNATELY","UNION","UNIT","UNITED","UNIVERSITY","UNLESS","UNLIKELY","UNTIL","UP","UPON","UPPER","URBAN","US","USE","USED","USEFUL","USER","USUAL","USUALLY","VALUE","VARIATION","VARIETY","VARIOUS","VARY","VAST","VEHICLE","VERSION","VERY","VIA","VICTIM","VICTORY","VIDEO","VIEW","VILLAGE","VIOLENCE","VISION","VISIT","VISITOR","VITAL","VOICE","VOLUME","VOTE","WAGE","WAIT","WALK","WALL","WANT","WAR","WARM","WARN","WASH","WATCH","WATER","WAVE","WAY","WE","WEAK","WEAPON","WEAR","WEATHER","WEEK","WEEKEND","WEIGHT","WELCOME","WELFARE","WELL","WEST","WESTERN","WHAT","WHATEVER","WHEN","WHERE","WHEREAS","WHETHER","WHICH","WHILE","WHILST","WHITE","WHO","WHOLE","WHOM","WHOSE","WHY","WIDE","WIDELY","WIFE","WILD","WILL","WIN","WIND","WINDOW","WINE","WING","WINNER","WINTER","WISH","WITH","WITHDRAW","WITHIN","WITHOUT","WOMAN","WONDER","WONDERFUL","WOOD","WORD","WORK","WORKER","WORKING","WORKS","WORLD","WORRY","WORTH","WOULD","WRITE","WRITER","WRITING","WRONG","YARD","YEAH","YEAR","YES","YESTERDAY","YET","YOU","YOUNG","YOUR","YOURSELF","YOUTH" };
	
	std::string text (textbytes, sizeof(textbytes));

	// 1786
	// Parse words
	std::vector<std::string> englishWords;
	//Tokenize(line, englishWords, "\","); 

	for (int i = 0; i < 1786; ++i)
		englishWords.push_back(std::string(words[i]));

	// Transform to lowercase
	for (std::vector<std::string>::iterator	it = englishWords.begin(); it != englishWords.end(); ++it)
		std::transform((*it).begin(), (*it).end(), (*it).begin(), ::tolower);

	// Prepare keys (only lowercase ascii characters)
	std::vector<std::string> keys;

	char buf[4];
	buf[3] = '\0';
	for (char i = 97; i <= 122; ++i)
	{
		for (char j = 97; j <= 122; ++j)
		{
			for (char k = 97; k <= 122; ++k)
			{
				memset(buf, 0, 3);

				buf[0] = i;
				buf[1] = j;
				buf[2] = k;

				keys.push_back(string(buf));		
			}
		}
	}

	// Try decription
	int threshold = 10;		// At least 2 english words found
	bool searching = true;
	string* bestkey = NULL;
	int bestrating = -1;

	for (std::vector<std::string>::iterator kIt = keys.begin(); kIt != keys.end(); ++kIt)
	{
		string& key = *kIt;

		string decriptedText = decode(text, key);

		std::transform(decriptedText.begin(), decriptedText.end(), decriptedText.begin(), ::tolower);

		// Compute rating
		int rating = 0;
		std::vector<std::string>::iterator wordIt;
		for (wordIt = englishWords.begin(); wordIt != englishWords.end(); ++wordIt)
		{
			string word = " " + *wordIt + " ";

			size_t found = decriptedText.find(word);
			if (found != string::npos)
			{
				rating++;
			}
		}

		if (rating > bestrating)
		{
			bestrating = rating;
			bestkey = &key;
		}

		if (rating > threshold) 
		{
			searching = false;
		}
	}

	if (bestkey)
	{
		std::string decoded = decode(text, *bestkey);

		// Find the sum of ASCII chars
		int sum = 0;
		const char* decoded_cstring = decoded.c_str();
		for (unsigned i = 0; i < decoded.size(); ++i)
			sum += decoded_cstring[i];

		return sum;
	}
	else return 0;
}

typedef std::vector<ZioUtils::Node*> NodeVector;
typedef std::vector<NodeVector*> Tree;


Tree* CreateTree(std::string& filePath)
{
	using std::ifstream;
	using std::string;
	using std::vector;
	using ZioUtils::Node;

	Tree* triangle = new Tree;

	// Parse file
	ifstream file;
	file.open(filePath.c_str(), ifstream::in);
	while (file.good())
	{
		// Get line
		string line;
		getline(file, line);

		// Add a new row in the triangle
		NodeVector* row = new NodeVector;
		triangle->push_back(row);

		// Parse line
		vector<string> tokens;
		ZioUtils::Tokenize(line, tokens, " ");

		vector<string>::iterator tokensIt;
		for (tokensIt = tokens.begin(); tokensIt != tokens.end(); ++tokensIt)
		{
			string& token = *tokensIt;
			Node* node = new Node(atoi(token.c_str()));
			row->push_back(node);
		}
	}

	// Create structure
	for (int i = triangle->size() - 2; i >= 0; --i)
	{
		NodeVector* row = triangle->at(i);
		for (unsigned j = 0; j < triangle->at(i)->size(); ++j)
		{
			Node* node = row->at(j);
			node->left = triangle->at(i+1)->at(j);
			node->right = triangle->at(i+1)->at(j+1);
		}
	}

	return triangle;
}

void FreeTree(Tree* tree)
{
	for (unsigned i = 0; i < tree->size(); ++i)
	{
		NodeVector* row = tree->at(i);

		for (unsigned j = 0; j < row->size(); ++j)
		{
			delete row->at(j);
		}

		delete row;
	}
}

RetType FilippoFantini::Problem18()
{
	std::string path = "data/problem18.txt";
	Tree* tree = CreateTree(path);
	RetType maxRoute = ZioUtils::MaxRoute(tree->at(0)->at(0));
	FreeTree(tree);
	return maxRoute;
}

RetType FilippoFantini::Problem67()
{
	std::string path = "data/problem67.txt";
	Tree* tree = CreateTree(path);
	RetType maxRoute = ZioUtils::MaxRoute(tree->at(0)->at(0));
	FreeTree(tree);
	return maxRoute;
}

// Problem 42: the dumb way :)
RetType FilippoFantini::Problem42()
{
	std::string line;
	std::ifstream file ("data/words.txt");
	while (!file.eof())
	{
		getline(file, line);
	}

	// Prepare triangle numbers
	std::vector<UInt32> triangleNumbers;
	for (UInt32 i = 0; i < 20; ++i)	// empiric
	{
		triangleNumbers.push_back(i * (i - 1) / 2);
	}

	// Parse names
	std::vector<std::string> words;

	int begin = 0;
	int end = 0;
	while (end >= 0)
	{
		begin = line.find("\"");
		end = line.find("\"", begin + 1);

		if (begin > -1 && end > -1)
		{
			std::string word = line.substr(begin + 1, end - begin - 1);
			line = line.erase(begin, end - begin + 1);
			words.push_back(word);
		}
	};

	// Calculate values
	RetType count = 0;
	std::vector<std::string>::iterator wordsIt;
	for (wordsIt = words.begin(); wordsIt != words.end(); ++wordsIt)
	{
		std::string& word = *wordsIt;
		// Calculate word value
		static std::string::const_iterator charIt;

		UInt32 wordValue = 0;
		for (charIt = word.begin(); charIt != word.end(); ++charIt)
		{
			wordValue += *charIt - 64;
		}
		//std::cout << word << " -> " << wordValue << std::endl;

		bool found = false;
		for (UInt32 i = 0; i < triangleNumbers.size(); ++i)
			if (triangleNumbers[i] == wordValue) found = true;

		if (found) ++count;
	}

	return count;
}

bool compare(const std::string& string1, const std::string& string2)
{
	return (string1.compare(string2) >= 0) ? false : true;
}

RetType FilippoFantini::Problem22()
{
	std::string line;
	std::ifstream file ("data/names.txt");
	while (!file.eof())
	{
		getline(file, line);
	}

	// Prepare triangle numbers
	std::vector<UInt32> triangleNumbers;
	for (UInt32 i = 0; i < 20; ++i)	// empiric
	{
		triangleNumbers.push_back(i * (i - 1) / 2);
	}

	// Parse names
	std::vector<std::string> names;

	int begin = 0;
	int end = 0;
	while (end >= 0)
	{
		begin = line.find("\"");
		end = line.find("\"", begin + 1);

		if (begin > -1 && end > -1)
		{
			std::string word = line.substr(begin + 1, end - begin - 1);
			line = line.erase(begin, end - begin + 1);
			names.push_back(word);
		}
	};

	// Sort
	std::sort(names.begin(), names.end(), compare);

	// Calculate value
	RetType total = 0;
	for (UInt32 i = 0; i < names.size(); ++i)
	{
		std::string& name = names[i];
		// Calculate word value
		UInt32 nameValue = 0;
		static std::string::const_iterator charIt;
		for (charIt = name.begin(); charIt != name.end(); ++charIt)
		{
			nameValue += *charIt - 64;
		}
		total += nameValue * (i + 1);
	}

	return total;
}

void pushNumber(std::vector<int> *buffer, UInt64 number)
{
	static std::vector<unsigned int> temp;
	temp.clear();

	while (number > 0)
	{
		int digit = number % 10;
		number /= 10;
		temp.push_back(digit);
	}

	for (int i = temp.size() - 1; i >= 0; --i)
		buffer->push_back(temp[i]);
}

RetType FilippoFantini::Problem40()
{
	// Generate fractional number
	std::vector<int> fractional;
	for (UInt64 i = 0; i < 200000; i++)
	{
		pushNumber(&fractional, i);
	}

	RetType product = 1;
	for (UInt32 i = 1; i <= 1000000; i *= 10)
	{
		product *= fractional[i-1];
	}
	
	return product;
}

RetType FilippoFantini::Problem25()
{
	ZioUtils::bcd n1 = 1;
	ZioUtils::bcd n2 = 2;
	RetType count = 2;

	while (n1.NumberOfDigits() < 1000)
	{
		ZioUtils::bcd temp = n2;
		n2 = n1 + n2;
		n1 = temp;
		count++;
	}

	return count;
}

RetType FilippoFantini::Problem20()
{
	UInt32 num = 100;
	ZioUtils::bcd a = num;
	for (int i = num-1; i > 0; --i)
	{
		ZioUtils::bcd b = i;
		a *= b;
	}

	RetType sum = 0;
	for (UInt32 i = 0; i < a.NumberOfDigits(); ++i)
		sum += a.GetDigit(i);

	return sum;
}

RetType FilippoFantini::Problem15()
{
	typedef UInt64* UInt64Array;

	const int lato = 20;

	UInt64Array* array = new UInt64Array[lato + 1];
	for (int i = 0; i <= lato; i++)
		array[i] = new UInt64[lato + 1];


	// Init
	for (int i = 0; i <= lato; i++)
		array[i][0] = array[0][i] = 1;

	// Calc
	for (int i = 1; i <= lato; i++)
		for (int j = 1; j <= lato; j++)
			array[i][j] = array[i-1][j] + array[i][j-1];

	RetType solution = array[lato][lato];

	// Free
	for (int i = 0; i <= lato; i++)
		delete[] array[i];

	delete[] array;

	return solution;
}

RetType FilippoFantini::Problem16()
{
	ZioUtils::bcd num = "2";
	int exp = 1000;
	for (int i = 1; i < exp; ++i)
	{
		num += num;
	}

	UInt32 sum = 0;
	for (UInt32 i = 0; i < num.NumberOfDigits(); i++)
	{
		UInt8 digit = num.GetDigit(i);
		sum += digit;
	}

	return sum;
}

RetType FilippoFantini::Problem17()
{
	RetType sum = 0;

	for (int i = 1; i <= 1000; i++)
	{
		std::string s = ZioUtils::NumberSpeller::SpellNumber(i);
		sum += s.length();
	}

	return sum;
}

RetType FilippoFantini::Problem13()
{
	// Compute
	ZioUtils::bcd sum = problem_data::problem13numbers[0];

	for (int i = 1; i < 100; i++)
	{
		ZioUtils::bcd num = problem_data::problem13numbers[i];
		sum += num;
	}
	
	// Convert back the last 10 digits
	RetType theNumber = 0;
	UInt16 j = 0;
	for (unsigned i = sum.NumberOfDigits() - 10; i < sum.NumberOfDigits(); ++i)
	{
		UInt64 digit = sum.GetDigit(i);
		for (int k = j; k > 0; k--) digit *= 10;
		theNumber += digit;
		j++;
	}

	return theNumber;
}

RetType FilippoFantini::Problem28()
{
	RetType sum = 1;
	int delta = 2;
	int count = 4;
	int value = 1;
	int size = 1001;

	for (int i = 2; i < size*2; i++)
	{
		value += delta;
		sum += value;
		
		count--;
		if (count == 0)
		{
			count = 4;
			delta += 2;
		}
	}

	return sum;
}

/*
The following iterative sequence is defined for the set of positive integers:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?
*/
inline UInt32 problem14fun(UInt32 n)
{
	UInt32 count = 1;

	while (n > 1)	// It's somehow guaranteed
	{
		count++;

		if (n % 2 == 0)
			n = n / 2;
		else
			n = 3 * n + 1;
	}

	return count;
}

RetType FilippoFantini::Problem14()
{
	UInt32 largestCount = 0;
	UInt32 largestNumber = 0;

	for (int i = 1000000; i > 1; i--)
	{
		UInt32 count = problem14fun(i);

		if (count > largestCount) 
		{
			largestCount = count;
			largestNumber = i;
		}
	}

	return largestNumber;
}


/*
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
*/
RetType FilippoFantini::Problem10()
{
	RetType sum = 2;
	UInt32 number = 3;

	while (number < 2000000)
	{
		if (math::IsPrime(number))
			sum += number;

		number += 2;
	}

	return sum;
}

/*
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13.

What is the 10001^(st) prime number?
*/
RetType FilippoFantini::Problem7()
{
	UInt32 primeNumber = 2;
	UInt32 number = 1;
	while (primeNumber <= 10001)
	{
		number += 2; // All primes except 2 are odd.
		if (math::IsPrime(number))
			primeNumber++;
	}
	return number;

}

RetType FilippoFantini::Problem6()
{
	RetType sumOfSquares = 0;
	RetType squareOfSum = 0;
	for (int i = 1; i <= 100; i++)
	{
		sumOfSquares += i*i;
		squareOfSum += i;
	}
	
	return squareOfSum*squareOfSum - sumOfSquares;
}

RetType FilippoFantini::Problem5()
{
	bool found = false;
	RetType lcm = 0;

	while (!found)
	{
		lcm += 20;	

		found = true;
		for (int i = 20-1; i > 0; --i)
		{
			if (lcm % i != 0)
			{
				found = false;
				break;
			}
		}
	}

	return lcm;
}


RetType FilippoFantini::Problem1()
{
	int answer = 0;
	for (int i = 0; i < 1000; i++)
	{
		if (IsMultipleOf(i, 3) || IsMultipleOf(i, 5))
			answer += i;
	}
	return answer;
}

RetType FilippoFantini::Problem2()
{
	int fib0 = 1;
	int fib1 = 2;

	int answer = 0;
	while (fib1 < 4000000)
	{
		int temp = fib0 + fib1;
		fib0 = fib1;
		fib1 = temp;
		if ( !math::IsOdd(fib0)) answer += fib0;
	}
	return answer;
}

RetType FilippoFantini::Problem3()
{
	RetType number = 600851475143;

	RetType maxDivisor = 0;
	UInt32 divisor = 2;
	while (number != 1)
	{
		if (number % divisor == 0)
		{
			number /= divisor;
		}
		else
		{
			divisor++;
			if (divisor > maxDivisor && math::IsPrime(divisor)) maxDivisor = divisor;
		}
	}

	return maxDivisor;
}



